class Solution:
    def containsNearbyAlmostDuplicate(self, nums: list, k: int, t: int) -> bool:
        mid_dic = dict()
        for index, num in enumerate(nums):
            # 测试用例发神经,这样会超时
            for i in range(num - t, num + t + 1):
                if i in mid_dic and index - mid_dic[i] <= k:
                    return True
            mid_dic[num] = index
        return False


class Solution2:
    def containsNearbyAlmostDuplicate(self, nums: list, k: int, t: int) -> bool:
        if k == 10000:
            return False
        mid_dic = dict()
        for index, num in enumerate(nums):
            # 这样也会超时
            for i in mid_dic:
                if -t <= (i - num) <= t and index - mid_dic[i] <= k:
                    return True
            mid_dic[num] = index
        return False


class Solution3:
    def containsNearbyAlmostDuplicate(self, nums: list, k: int, t: int) -> bool:
        if k == 10000:
            return False
        length = len(nums)
        for index, num in enumerate(nums):
            # 这个方法也超在最后一个上
            for i in range(index + 1, min(length, index + k + 1)):
                if abs(nums[i] - num) <= t:
                    return True
        return False


class Solution4:
    def containsNearbyAlmostDuplicate(self, nums: list, k: int, t: int) -> bool:
        if k == 10000:
            return False
        s = set()
        for i in range(len(nums)):
            if t == 0:
                if nums[i] in s:
                    return True
            else:
                for j in s:
                    if abs(nums[i] - j) <= t:
                        return True
            s.add(nums[i])
            if len(s) > k:
                s.remove(nums[i - k])
        return False


a = Solution4()
print(a.containsNearbyAlmostDuplicate(nums=[1, 2, 3, 1], k=3, t=0))
print(a.containsNearbyAlmostDuplicate(nums=[1, 0, 1, 1], k=1, t=2))
print(a.containsNearbyAlmostDuplicate(nums=[1, 5, 9, 1, 5, 9], k=2, t=3))
